﻿/*
 * 
 * User: Gavin Mead
 * Date: 12/1/2009
 * Time: 2:45 PM
 * 
 * 
 */

using System;
using System.Collections.Generic;
using NUnit.Framework;

using GraphLibrary;

namespace GraphLibraryTests
{
    [TestFixture]
    public class DepthFirstTraverserTests
    {
        [Test]
        [Description("Verifies that an exception is thrown if the startVertex "  +
                     "is null")]
        [ExpectedException(typeof(ArgumentNullException))]
        public void NullIVertexIdTest()
        {
            IGraph<int,int> graph = GraphFactory<int, int>.CreateGraph(GraphTypes.Undirected);
            
            IGraphTraverser<int, int> traverser = new DepthFirstTraverser<int, int>();
            traverser.Graph = graph;
            IList<int> results = traverser.Traverse(null);   //Throws exception
        }

        [Test]
        [Description("Verifies that an exception is thrown if the vertexId does " +
                     "exist in the provided graph")]
        [ExpectedException(typeof(ArgumentException))]
        public void UnknownVertexIdTest()
        {
            IGraph<int,int> graph = GraphFactory<int, int>.CreateGraph(GraphTypes.Undirected);
            
            IGraphTraverser<int, int> traverser = new DepthFirstTraverser<int, int>();
            traverser.Graph = graph;
            
            IList<int> result = traverser.Traverse(new BaseVertexId()); //Throws exception
        }
        
        [Test]
        [Description("Verifies that an exception is thrown if the Graph property " +
                     "has not been set on the traverser.")]
        [ExpectedException(typeof(InvalidOperationException))]
        public void GraphPropertyNotSetTest()
        {
            IGraphTraverser<int, int> traverser = new DepthFirstTraverser<int, int>();
            IList<int> result = traverser.Traverse(new BaseVertexId());
        }
        
        [Test]
        [Description("Verifies that a list of vertex data is returned in the expected " +
                     "depth first traversal order of an Undirected graph.")]
        public void GoodUnidirectedTraversalTest()
        {
            IGraph<int, int> graph = GraphFactory<int, int>.CreateGraph(GraphTypes.Undirected);
            
            IVertexId v1 = graph.AddVertex(1);
            IVertexId v2 = graph.AddVertex(2);
            IVertexId v3 = graph.AddVertex(3);
            IVertexId v4 = graph.AddVertex(4);
            IVertexId v5 = graph.AddVertex(5);
            
            IEdgeId v1Tov2 = graph.AddEdge(1, v1, v2);
            IEdgeId v2Tov4 = graph.AddEdge(2, v2, v4);
            IEdgeId v2Tov3 = graph.AddEdge(3, v2, v3);
            IEdgeId v1Tov3 = graph.AddEdge(4, v1, v3);
            IEdgeId v3Tov4 = graph.AddEdge(5, v3, v4);
            IEdgeId v3Tov5 = graph.AddEdge(6, v3, v5);
            
            IList<int> expectedVertexOrder = new List<int>();
            expectedVertexOrder.Add(1);
            expectedVertexOrder.Add(3);
            expectedVertexOrder.Add(5);
            expectedVertexOrder.Add(4);
            expectedVertexOrder.Add(2);
            
            IGraphTraverser<int, int> traverser = new DepthFirstTraverser<int, int>();
            traverser.Graph = graph;
            
            IList<int> results = traverser.Traverse(v1);
            
            Assert.AreEqual(expectedVertexOrder.Count, results.Count);
            for (int i = 0; i < expectedVertexOrder.Count; i++)
            {
                Assert.AreEqual(expectedVertexOrder[i], results[i]);
            }
        }
        
        [Test]
        [Description("Verifies that a list of vertex data is returned in the expected " +
                     "depth first traversal order of a Directed graph")]
        public void GoodDirectedGraphTest()
        {
            IGraph<int, int> graph = GraphFactory<int, int>.CreateGraph(GraphTypes.Directed);
            
            IVertexId v1 = graph.AddVertex(1);
            IVertexId v2 = graph.AddVertex(2);
            IVertexId v3 = graph.AddVertex(3);
            IVertexId v4 = graph.AddVertex(4);
            IVertexId v5 = graph.AddVertex(5);
            
            IEdgeId v1Tov2 = graph.AddEdge(1, v1, v2);
            IEdgeId v1Tov3 = graph.AddEdge(2, v1, v3);
            IEdgeId v2Tov4 = graph.AddEdge(3, v2, v4);
            IEdgeId v2Tov3 = graph.AddEdge(4, v2, v3);
            IEdgeId v3Tov5 = graph.AddEdge(5, v3, v5);
            IEdgeId v5Tov4 = graph.AddEdge(6, v5, v4);
            IEdgeId v3Tov2 = graph.AddEdge(7, v3, v2);
            
            IList<int> expectedVertexOrder = new List<int>();
            expectedVertexOrder.Add(1);
            expectedVertexOrder.Add(3);
            expectedVertexOrder.Add(2);
            expectedVertexOrder.Add(4);
            expectedVertexOrder.Add(5);
            
            IGraphTraverser<int, int> traverser = new DepthFirstTraverser<int, int>();
            traverser.Graph = graph;
            
            IList<int> results = traverser.Traverse(v1);
            
            Assert.AreEqual(expectedVertexOrder.Count, results.Count);
            for (int i = 0; i < expectedVertexOrder.Count; i++)
            {
                Assert.AreEqual(expectedVertexOrder[i], results[i]);
            }
        }
        
    }
}
